﻿<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
<head>
    <title></title>
</head>
<body>
    <table>
        <tr>
            <td align="justify">
            <p align="center" style="font-size: large"><b>  Method Iteration </b></p>
                <p>
                    &nbsp;&nbsp;&nbsp;In computational mathematics, an iterative method attempts to
                    solve a problem (for example, finding the root of an equation or system of equations)
                    by finding successiveapproximations to the solution starting from an initial guess.
                    This approach is in contrast to direct methods, which attempt to solve the problem
                    by a finite sequence of operations, and, in the absence of rounding errors, would
                    deliver an exact solution (like solving a linear system of equations Ax = b by Gaussian
                    elimination). Iterative methods are usually the only choice for nonlinear equations.
                    However, iterative methods are often useful even for linear problems involving a
                    large number of variables (sometimes of the order of millions), where direct methods
                    would be prohibitively expensive (and in some cases impossible) even with the best
                    available computing power.</p>
                <p align="center">
                    <b><b>Attractive fixed points</b></b></p>
                <p>
                    &nbsp;&nbsp;&nbsp;If an equation can be put into the form f(x) = x, and a solution
                    x is an attractive fixed point of the function f, then one may begin with a point
                    x1 in the basin of attraction of x, and let xn+1 = f(xn) for n ≥ 1, and the sequence
                    {xn}n ≥ 1 will converge to the solution x. If the function f is continuously differentiable,
                    a sufficient condition for convergence is that the spectral radius of the derivative
                    is strictly bounded by one in a neighborhood of the fixed point. If this condition
                    holds at the fixed point, then a sufficiently small neighborhood (basin of attraction)
                    must exist.</p>
                <p align="center">
                    <b><b>Linear systems</b></b></p>
                <p>
                    &nbsp;&nbsp;&nbsp;In the case of a system of linear equations, the two main classes
                    of iterative methods are the stationary iterative methods, and the more general
                    Krylov subspacemethods.</p>
                <p align="center">
                    <b><b>Stationary iterative methods</b></b></p>
                <p>
                    &nbsp;&nbsp;&nbsp;Stationary iterative methods solve a linear system with an operator
                    approximating the original one; and based on a measurement of the error (the residual),
                    form a correction equation for which this process is repeated. While these methods
                    are simple to derive, implement, and analyse, convergence is only guaranteed for
                    a limited class of matrices. Examples of stationary iterative methods are the Jacobi
                    method, Gauss–Seidel method and the Successive over-relaxation method.</p>
                <p align="center">
                    <b><b>Krylov subspace methods</b></b></p>
                <p>
                    &nbsp;&nbsp;&nbsp;Krylov subspace methods form an orthogonal basis of the sequence
                    of successive matrix powers times the initial residual (the Krylov sequence). The
                    approximations to the solution are then formed by minimizing the residual over the
                    subspace formed. The prototypical method in this class is the conjugate gradient
                    method (CG). Other methods are the generalized minimal residual method (GMRES) and
                    the biconjugate gradient method (BiCG).</p>
                <p align="center">
                    <b><b>Convergence</b></b></p>
                <p>
                    &nbsp;&nbsp;&nbsp;Since these methods form a basis, it is evident that the method
                    converges in N iterations, where N is the system size. However, in the presence
                    of rounding errors this statement does not hold; moreover, in practice N can be
                    very large, and the iterative process reaches sufficient accuracy already far earlier.
                    The analysis of these methods is hard, depending on a complicated function of the
                    spectrum of the operator.</p>
                <p align="center">
                    <b><b>Preconditioners</b></b></p>
                <p>
                    &nbsp;&nbsp;&nbsp;The approximating operator that appears in stationary iterative
                    methods can also be incorporated in Krylov subspace methods such as GMRES (alternatively,
                    preconditionedKrylov methods can be considered as accelerations of stationary iterative
                    methods), where they become transformations of the original operator to a presumably
                    better conditioned one. The construction of preconditioners is a large research
                    area.</p>
                <p align="center">
                    <b><b>History</b></b></p>
                <p>
                    &nbsp;&nbsp;&nbsp;Probably the first iterative method for solving a linear system
                    appeared in a letter of Gauss to a student of his. He proposed solving a 4-by-4
                    system of equations by repeatedly solving the component in which the residual was
                    the largest. The theory of stationary iterative methods was solidly established
                    with the work of D.M. Young starting in the 1950s. The Conjugate Gradient method
                    was also invented in the 1950s, with independent developments by Cornelius Lanczos,
                    Magnus Hestenes and Eduard Stiefel, but its nature and applicability were misunderstood
                    at the time. Only in the 1970s was it realized that conjugacy based methods work
                    very well for partial differential equations, especially the elliptic type.
                </p>
            </td>
        </tr>
    </table>
</body>
</html>
